package com.fe.class03;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 把链表中的给定值都删除
 * @Author sosuke :-)
 * @Date 2021/12/7 06:59
 */
public class Code03_DeleteGivenValue {

    public static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 注意head节点可能发生改变
     * @param head
     * @param value
     * @return
     */
    public static Node removeValue(Node head, int value) {
        // 移动head到第一个不用删除的node，即要返回的head节点，确定后不能移动
        while (null != head) {
            if (value != head.data) {
                break;
            }
            head = head.next;
        }
        /**
         * 此时head已确定，不能移动，定义两个指针，一个指向当前cur（用于遍历），一个指向之前要保留的节点pre
         * 如果遇到了指定值的节点，则跳过，否则将pre移动到cur
         */
        Node pre = head; // 指向上次被保留的的节点
        Node cur = head; // 指向当前节点
        while (null != cur) {
            if (cur.data == value) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) {
        int testTimes = 100000;
        int maxSize = 10;
        int maxValue = 100;
        for (int i = 0; i < testTimes; i++) {
            int value = (int) (Math.random() * (maxValue + 1));
            Node head = generateRandomLinkedList(maxSize, maxValue, value);
            System.out.println("value = " + value);
            printLinkedList(head);
            List<Node> originLinkedList = getOriginLinkedList(head);
            Node head1 = testRemoveValue(originLinkedList, value);
            Node head2 = removeValue(head, value);
            // System.out.print("head1===>");
            // printLinkedList(head1);
            // System.out.print("head2===>");
            // printLinkedList(head2);
            if (!nodeEqual(head1, head2)) {
                System.out.println("Fuck!");
                System.out.print("head1===>");
                printLinkedList(head1);
                System.out.print("head2===>");
                printLinkedList(head2);
                return;
            }
        }
        System.out.println("Nice!");
        int value = (int) (Math.random() * (maxValue + 1));
        Node head = generateRandomLinkedList(maxSize, maxValue, value);
        System.out.println("value = " + value);
        printLinkedList(head);
        Node newHead = removeValue(head, value);
        printLinkedList(newHead);
    }

    /**
     * 判断两个单链表是否相等
     * @param head1
     * @param head2
     * @return
     */
    public static boolean nodeEqual(Node head1, Node head2) {
        Node p1 = head1;
        Node p2 = head2;
        while (p1 != null && p2 != null) {
            if (p1.data != p2.data) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1 == null && p2 == null;
    }

    /**
     * 使用容器来完成功能
     *
     * @param originLinkedList
     * @param value
     * @return
     */
    public static Node testRemoveValue(List<Node> originLinkedList, int value) {
        if (null == originLinkedList || originLinkedList.size() == 0) return null;
        originLinkedList.removeIf(cur -> cur.data == value);
        if (originLinkedList.size() > 0) {
            for (int i = 0; i < originLinkedList.size() - 1; i++) {
                Node cur = originLinkedList.get(i);
                cur.next = originLinkedList.get(i + 1);
            }
            return originLinkedList.get(0);
        }
        return null;
    }

    /**
     * 把链表按顺序添加到容器中
     *
     * @param head
     * @return
     */
    public static List<Node> getOriginLinkedList(Node head) {
        List<Node> list = new ArrayList<>();
        for (; head != null; head = head.next) {
            list.add(head);
        }
        return list;
    }

    // 打印单链表
    public static void printLinkedList(Node head) {
        if (null == head) {
            System.out.println("\"null\"");
            return;
        }
        Node cur = head;
        while (null != cur) {
            System.out.print(cur.data + "--->");
            System.out.print(cur.next == null ? "null" : "");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 随机生成单链表，加入特定值的节点
     *
     * @param maxSize
     * @param maxValue
     * @return
     */
    public static Node generateRandomLinkedList(int maxSize, int maxValue, int value) {
        // [1,maxSize]
        int size = (int) ((Math.random() * maxSize) + 1);
        if (size == 0) return null;
        // 要返回的head节点，不能移动
        Node head = new Node((int) (Math.random() * (maxValue + 1)));
        head = Math.random() < 0.5 ? new Node(value) : head;
        size--;
        // 定义指针用于添加节点后向后移动
        Node pre = head;
        for (int i = 0; i < size; i++) {
            Node cur = new Node((int) (Math.random() * (maxValue + 1)));
            cur = Math.random() < 0.4 ? cur : new Node(value);
            pre.next = cur;
            pre = cur;
        }
        return head;
    }


}
